◀ Prev · Parts · Full · Next ▶

Often, the Boolean domain is taken as { − − 1 , 1 } {\displaystyle \{-1,1\}} , with false ("0") mapping to 1 and true ("1") to −1 (see Analysis of Boolean functions). The polynomial corresponding to g ( x ) : { − − 1 , 1 } n → → { − − 1 , 1 } {\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}} is then given by: g ∗ ∗ ( x ) = ∑ ∑ a ∈ ∈ { − − 1 , 1 } n g ( a ) ∏ ∏ i : a i = − − 1 1 − − x i 2 ∏ ∏ i : a i = 1 1 + x i 2 {\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}} Using the symmetric Boolean domain simplifies certain aspects of the analysis, since negation corresponds to multiplying by −1 and linear functions are monomials (XOR is multiplication). This polynomial form thus corresponds to the Walsh transform (in this context also known as Fourier transform) of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values E ( X ) = P ( X = 1 ) − − P ( X = − − 1 ) ∈ ∈ [ − − 1 , 1 ] {\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]} (see piling-up lemma for an example).

◀ Prev · Parts · Full · Next ▶